package com.algrithom.graph.shortestpath;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.common.model.Edge;
import com.common.model.Vertex;

/**
 * 解决多源最短路径
 *
 * @author think
 * @version 1.0.0
 * @since 2020/2/12
 */
public class Floyd {
    
    public static void main(String[] args){
        List<Vertex> vertices = new ArrayList<>();
        List<Edge> edges = new ArrayList<>();
        
        Vertex preVertex = Vertex.builder().number(0).build();
        Vertex nextVertex = Vertex.builder().number(1).weight(10).build();
        preVertex.setNextNode(nextVertex);
        Edge edge = new Edge(0,1,10);
        edges.add(edge);
        
        nextVertex = Vertex.builder().number(3).weight(8).build();
        preVertex.getNextNode().setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(0,3,8);
        edges.add(edge);
        
        preVertex = Vertex.builder().number(1).build();
        nextVertex = Vertex.builder().number(5).weight(2).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(1,5,2);
        edges.add(edge);
        
        preVertex = Vertex.builder().number(2).build();
        nextVertex = Vertex.builder().number(1).weight(1).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(2,1,1);
        edges.add(edge);
        
        preVertex = Vertex.builder().number(3).build();
        nextVertex = Vertex.builder().number(4).weight(1).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(3,4,1);
        edges.add(edge);
        
        preVertex = Vertex.builder().number(4).build();
        nextVertex = Vertex.builder().number(5).weight(-1).build();
        preVertex.setNextNode(nextVertex);
        edge = new Edge(4,5,-1);
        edges.add(edge);
        
        nextVertex = Vertex.builder().number(1).weight(-4).build();
        preVertex.getNextNode().setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(4,1,-4);
        edges.add(edge);
        
        preVertex = Vertex.builder().number(5).build();
        nextVertex = Vertex.builder().number(2).weight(-2).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        edge = new Edge(5,2,-2);
        edges.add(edge);
        
        getSmallestDistanceFloyd(vertices,edges);
    }
    
    public static Map<Vertex,HashMap<Vertex,Double>> getSmallestDistanceFloyd(List<Vertex> vertexSet,List<Edge> edges){
        //第一个 result，key为出发点，value是map，这个map的key是结束点，value是出发点到结束点的最短距离
        Map<Vertex,HashMap<Vertex,Double>> result = new HashMap<>();
        //第二个 path，key为出发点，value是map，这个map的key是结束点，value是出发点到结束点的最短距离的路径的最后的中转节点
        Map<Vertex,HashMap<Vertex,Vertex>> path = new HashMap<>();
        
        for (Vertex begin : vertexSet) {
            HashMap<Vertex,Double> distanceMap = new HashMap<>();
            HashMap<Vertex,Vertex> pathMap = new HashMap<>();
            for (Vertex end : vertexSet) {
                //一开始，result里的value为maxDouble(到自己的value为0），path里的value是结束点
                distanceMap.put(end,Double.MAX_VALUE);
                pathMap.put(end,end);
            }
            //result里的value为maxDouble(到自己的value为0），path里的value是结束点
            distanceMap.put(begin,0.0);
            result.put(begin,distanceMap);
            path.put(begin,pathMap);
        }
        
        for (Vertex begin : vertexSet) {
            HashMap<Vertex,Double> distanceMap = result.get(begin);
            for (Edge edge : edges) {
                //用图里的所有的边对result做初始化，当不经过任意第三节点时，其最短路径为初始路径，只对图里先有的只经过两点的边，对result里的value更新
                distanceMap.put(Vertex.builder().number(edge.getDstNode()).build(),(double)edge.getWeight());
            }
            result.put(begin,distanceMap);
        }
        
        for (Vertex mid : vertexSet) {
            for (Vertex begin : vertexSet) {
                HashMap<Vertex,Double> distanceMap = result.get(begin);
                HashMap<Vertex,Vertex> pathMap = path.get(begin);
                for (Vertex end : vertexSet) {
                    Double beginEnd = distanceMap.get(end);
                    Double beginMid = distanceMap.get(mid);
                    Double midEnd = result.get(mid).get(end);
                    if (beginMid == Double.MAX_VALUE || midEnd == Double.MAX_VALUE || beginMid + midEnd > beginEnd) {
                        //如果通过中转点不行，或者通过中转点的距离大于原先距离，就不考虑这个中转点
                        continue;
                    }
                    //让i到j的min距离=i到1号的min距离 + 1号到j的min距离，并且i到j的最后的中转节点为1号节点
                    distanceMap.put(end,beginMid + midEnd);
                    pathMap.put(end,mid);
                }
                result.put(begin,distanceMap);
                path.put(begin,pathMap);
            }
        }
        
        for (Vertex begin : vertexSet) {
            HashMap<Vertex,Double> distanceMap = result.get(begin);
            HashMap<Vertex,Vertex> pathMap = path.get(begin);
            for (Vertex end : vertexSet) {
                System.out.println("从顶点:" + begin.getNumber() + " ，到顶点：" + end.getNumber() + " ，最短距离为：" + distanceMap.get(end) + " ，最后中转点为:" + pathMap.get(end).getNumber());
            }
        }
        
        return result;
    }
}
